// https://www.lintcode.com/problem/remove-duplicate-letters/

public class Solution {
    /**
     * @param s: a string
     * @return: return a string
     */
    public String removeDuplicateLetters(String s) {
        // write your code here
        StringBuilder sb = new StringBuilder();
        HashMap<Character, Integer> counting = new HashMap<>();
        HashSet<Character> visited = new HashSet();
        for (int i = 0; i < s.length(); ++i) {
            Character c = s.charAt(i);
            if (!counting.containsKey(c)) {
                counting.put(c, 0);
            }
            counting.put(c, counting.get(c) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            Character c = s.charAt(i);
            counting.put(c, counting.get(c) - 1);
            if (visited.contains(c)) {
                continue;
            }
            // 如果前一个字符比当前的c大，且后面还会出现，那么就扔了。
            while ((sb.length() > 0) && (counting.get(sb.charAt(sb.length() - 1)) > 0) && (sb.charAt(sb.length() - 1) > c)) {
                visited.remove(sb.charAt(sb.length() - 1));
                sb.deleteCharAt(sb.length() - 1);
            }
            sb.append(c);
            visited.add(c);
        }
        return sb.toString();
    }
}